class Solution {
    /*
        思路：使用bfs算法
        坑点：root可能为null
        时间复杂度：O(n) 每个点最多遍历一次
        空间复杂度：O(n) 队列元素不超过n（应该是最大的层数），渐进复杂度
    */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root!=null) q.add(root); // 坑点
        while( !q.isEmpty() ){
            List<Integer> list = new ArrayList<>();
            int len = q.size();
            for(int i=1; i<=len; i++){
                TreeNode tmp = q.poll();
                list.add(tmp.val);
                if( tmp.left!=null )  q.offer(tmp.left);
                if( tmp.right!=null ) q.offer(tmp.right);
            }
            res.add(list);
            if(len<=0) break;
        }
        return res;
    }
}

class Solution {
    /**
        思路：dfs+递归实现+不使用队列实现
    **/
   public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(0, root, ans);
        return ans;
    }

    public void dfs(int level, TreeNode root, List<List<Integer>> ans) {
        if (root == null)
            return;
        if (level >= ans.size())
            ans.add(new ArrayList<>());
        ans.get(level).add(root.val);
        dfs(level + 1, root.left, ans);
        dfs(level + 1, root.right, ans);
    }
}